<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.1.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">
  <meta name="google-site-verification" content="T1Dbmn0YmNZwwxNqq98b7FvVCsxbeIChYP6H75TZjdk">
  <meta name="baidu-site-verification" content="code-86L5xW0tJy">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14.0/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"www.whatsblockchain.com","root":"/","scheme":"Gemini","version":"8.0.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"}};
  </script>

  <meta name="description" content="分布式系统介绍 长期以来学习掌握分布式系统的知识非常庞杂混乱，要确定分布式系统算法的分类，主要依据是搞清楚算法的各种属性。例如计时模型timing model; 进程间通讯interprocess communication 和失败模型failure model等等。">
<meta property="og:type" content="article">
<meta property="og:title" content="【分布式共识一】分布系统及共识介绍">
<meta property="og:url" content="https://www.whatsblockchain.com/posts/ec5b8a8d.html">
<meta property="og:site_name" content="区块链大杂烩">
<meta property="og:description" content="分布式系统介绍 长期以来学习掌握分布式系统的知识非常庞杂混乱，要确定分布式系统算法的分类，主要依据是搞清楚算法的各种属性。例如计时模型timing model; 进程间通讯interprocess communication 和失败模型failure model等等。">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2017-07-14T16:00:00.000Z">
<meta property="article:modified_time" content="2020-09-16T06:58:46.633Z">
<meta property="article:author" content="吴寿鹤">
<meta property="article:tag" content="分布式共识">
<meta property="article:tag" content="区块链共识算法">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="https://www.whatsblockchain.com/posts/ec5b8a8d.html">


<script class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>【分布式共识一】分布系统及共识介绍 | 区块链大杂烩</title>
  
    <script async src="https://www.googletagmanager.com/gtag/js?id=UA-145440251-1"></script>
    <script>
      if (CONFIG.hostname === location.hostname) {
        window.dataLayer = window.dataLayer || [];
        function gtag(){dataLayer.push(arguments);}
        gtag('js', new Date());
        gtag('config', 'UA-145440251-1');
      }
    </script>


  <script>
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?9af0452214522472f44968f5a652e2f0";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end --></head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">区块链大杂烩</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">你想要的这里都有</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
  </ul>
</nav>




</div>
        
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <section class="post-toc-wrap sidebar-panel">
          <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F%E4%BB%8B%E7%BB%8D"><span class="nav-number">1.</span> <span class="nav-text">分布式系统介绍</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%AE%A1%E6%97%B6%E6%A8%A1%E5%9E%8Btiming-model"><span class="nav-number">2.</span> <span class="nav-text">计时模型timing model</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%BF%9B%E7%A8%8B%E9%97%B4%E9%80%9A%E8%AE%AF"><span class="nav-number">3.</span> <span class="nav-text">进程间通讯</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%B1%E8%B4%A5%E6%A8%A1%E5%9E%8B"><span class="nav-number">4.</span> <span class="nav-text">失败模型</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%B1%E8%B4%A5%E6%8E%A2%E6%B5%8B"><span class="nav-number">5.</span> <span class="nav-text">失败探测</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%A2%86%E5%AF%BC%E4%BA%BA%E9%80%89%E4%B8%BEleader-election"><span class="nav-number">6.</span> <span class="nav-text">领导人选举LEADER ELECTION</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%80%E8%87%B4%E5%85%B1%E8%AF%86consensus"><span class="nav-number">7.</span> <span class="nav-text">一致共识CONSENSUS</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F%E7%9A%84%E6%97%B6%E9%97%B4"><span class="nav-number">8.</span> <span class="nav-text">分布式系统的时间</span></a></li></ol></div>
      </section>
      <!--/noindex-->

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">吴寿鹤</p>
  <div class="site-description" itemprop="description">代码之美，在于架构，架构之美，在于抽象</div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">21</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">7</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">11</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </section>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">
      

      

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://www.whatsblockchain.com/posts/ec5b8a8d.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="吴寿鹤">
      <meta itemprop="description" content="代码之美，在于架构，架构之美，在于抽象">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="区块链大杂烩">
    </span>

    
    
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          【分布式共识一】分布系统及共识介绍
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2017-07-15 00:00:00" itemprop="dateCreated datePublished" datetime="2017-07-15T00:00:00+08:00">2017-07-15</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-09-16 14:58:46" itemprop="dateModified" datetime="2020-09-16T14:58:46+08:00">2020-09-16</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F%E5%85%B1%E8%AF%86/" itemprop="url" rel="index"><span itemprop="name">分布式共识</span></a>
        </span>
    </span>

  
    <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span id="busuanzi_value_page_pv"></span>
    </span>
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>3.9k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>4 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="分布式系统介绍">分布式系统介绍</h2>
<p>长期以来学习掌握分布式系统的知识非常庞杂混乱，要确定分布式系统算法的分类，主要依据是搞清楚算法的各种属性。例如计时模型timing model; 进程间通讯interprocess communication 和失败模型failure model等等。</p>
<a id="more"></a>
<p>涉及的主要概念包括：</p>
<ol type="1">
<li><p>定时模型（Timing Model）</p></li>
<li><p>进程间通信（Interprocess Communication）</p></li>
<li><p>失效模式（Failure Modes）</p></li>
<li><p>失效检测器（Failure Detectors）</p></li>
<li><p>领导人选举（Leader Election）</p></li>
<li><p>共识（Consensus）</p></li>
<li><p>法定人数（Quorums）</p></li>
<li><p>分布式系统中的时间</p></li>
</ol>
<h2 id="计时模型timing-model">计时模型timing model</h2>
<p>计时模型分同步，异步两种，这几种模型都有时间计时这个共同特点。</p>
<p><strong>同步模型</strong> 在同步分布式系统中消息传递时间的上限是已知的。</p>
<p><strong>异步模型</strong> 异步分布式系统中消息可能在任何时间送达。</p>
<p>在同步分布式系统中，由于消息传递时间的上限已知，则可以根据超时来检测进程故障（非拜占庭故障），大大简化了分布式算法的设计，但遗憾的是，大部分实际的分布式系统往往是异步的，比如互联网就是异步分布式系统，如果为异步分布式系统中设计分布式算法，必须意识到消息可能延迟任意长的时间到达。</p>
<h2 id="进程间通讯">进程间通讯</h2>
<p>进程之间是如何通讯的，这里有<strong>消息传递模型</strong>和<strong>共享内存模型</strong>，前者是通过消息发送通讯，后者是访问内存中共享变量共享数据进行通讯。这里进程有服务器节点的意思，一个进程可能代表分布式场景的一台服务器。</p>
<p><strong>消息传递</strong>最难的是不能发送重复消息，每次只能精确一次传递，这里有很多设计，比如Perfect Links（可以理解为进程之间的信道） 抽象可以保证，但是它不能正常反映现实世界，虽然不真实，但是有用，我们可以使用Perfect Links 证明一个问题不可能被解决，然后我们就知道其他相关问题也没有答案。消息传递总是可以被想象为FIFO之类队列或堆栈。</p>
<p><strong>共享内存</strong>是我们编程常用的方式，需要在一台服务器内才能完成。我们可以使用消息传递算法完成分布式情况下的内存共享对象，比如读写注册器，调用一个服务之间需要查询这个服务在哪个服务器上，负载平衡器也是一个读写注册器，是一个全局共享的内存。</p>
<p>在理解基于消息传递模型的算法时，还必须弄清楚进程之间是哪一种链接（可以理解为进程之间的信道）。不同种类的链接抽象为算法提供的保证也不相同。例如，完美链接能够保证消息的可靠送达，不会重复发送消息；它保证消息会且只会一次送达。显然，现实世界并非如此。当算法设计者在设计尽量接近真实的模型时，他们会使用其他类型的链接抽象。请牢记，即使完美链接并非那么真实，它仍然有用。例如，如果我们能证明，即使链接是完美的我们也无法解决某个问题，那么所有的相关问题也将是不可解的。在讨论链接时，研究者通常会假定消息顺序是“先入先出”的， <a target="_blank" rel="noopener" href="http://web.stanford.edu/class/cs347/reading/zab.pdf">Zab</a> 就是一个例子。</p>
<h2 id="失败模型">失败模型</h2>
<p>进程的失败模型是分布式系统模型的一个属性，它是对进程失效种类的假设。</p>
<p>分布式模型总是必须考虑进程失败的情况，在<strong>crash-stop失败模型</strong>中，一个进程假设为一直是正确，直至它崩溃，一旦它崩溃，就永远不会恢复；也有<strong>crash-recovery</strong> <strong>模型</strong>，进程能够在失败以后恢复，在这种情况下，一些算法来保证进程恢复到其失败之前的状态，这可以通过从持久层读取状态完成，或者通过和一个集群小组中的其他进程通讯方式完成。注意这里有不同集群组算法，一个进程崩溃后，恢复其状态的进程不会再被认为是之前同样的进程，这取决于动态组还是固定组这两种算法。</p>
<p>失败模型也包括：一个进程如果无法接受和发送消息，被称为遗漏<strong>omission failure mode</strong>，遗漏模型也有不同种类，一个进程无法接受和发送消息很重要吗？想象一组进程实现一个分布式缓存，如果一个进程无法回复同一组的其他进程，即使能够接受来自它们的请求，这也意味着这个进程能够接受外部消息更新自己的状态，其实也就意味着它能回复来自客户端的读请求，也就是说，虽然它自己不能主动回复客户端的请求，但是可以接受客户端的主动读取请求。</p>
<p>一个复杂失败模型是<strong>拜占庭Byzantine</strong> <strong>或称为任意失败模型</strong>，进程会发送错误信息到对方，它们会模仿发送正确数据，但是实际已经篡改了本地数据库的内容。</p>
<p>设计分布式系统时，我们需要对付这些失败模型。</p>
<h2 id="失败探测">失败探测</h2>
<p>有了定时模型和进程失效模式的假设，我们就可以构建报告系统状态的抽象——失败检测器，即检测某个进程是否已经崩溃，或者怀疑这个进程已经崩溃。完美失效检测器从不虚报进程失效。</p>
<p>我们希望在进程崩溃失败时及时发现，比如crash-stop失败模型加上同步系统，我们能够使用timeout；如果我们定期让进程ping到一个专门的失败探测器，我们就能精确知道那个进程是否正常，如果过了timeout时间没有Ping访问，那么我们就可以认为那台进程服务器崩溃了。</p>
<p>更真实情况是，假设一个消息到达目标需要确定的时间，确定好一个进程执行一个步骤需要多长时间，那么就可以使用timeout进行衡量计算。</p>
<p>失败模型探测有两个属性策略：</p>
<ol type="1">
<li><p><strong>Strong Completeness强完整性</strong>：每个失败的进程会永久被其他正确进程怀疑。</p></li>
<li><p><strong>Eventual Strong Accuracy最终强精确度</strong>，没有一个进程被任何正确的进程怀疑。</p></li>
</ol>
<p>失败检测器是异步模型中解决共识问题的关键。在 <a target="_blank" rel="noopener" href="http://cs-www.cs.yale.edu/homes/arvind/cs425/doc/fischer.pdf">FLP</a> 论文中，提出了很多著名的不可能性结果。这篇论文指出，在异步的分布式系统中，如果进程有可能失效，那么就不可能达成共识。要达成共识，就必须为系统引入一个<a target="_blank" rel="noopener" href="http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p225-chandra.pdf">能够规避上述问题的失效检测器</a>。</p>
<p>当一个进程被其他进程怀疑时，这些进程就不可能达成共识consensus ，而在分布式系统中使用异步模型是必须要达成共识，也就是每个进程内部状态通过异步消息传递后，最终其他进程的状态会和最初发送消息的那个进程内部状态一致，这称为达成共识，但是因为有进程存在失败崩溃的可能，所以，在这个达成共识的消息传递过程中，如何确保进程之间的信任，不怀疑对方，从而确保消息传递成功，那么引入失败探测器是可以规避这个问题的。</p>
<h2 id="领导人选举leader-election">领导人选举LEADER ELECTION</h2>
<p>与失败检测相反的一个问题是，如何判定一个进程没有崩溃，它因此能够正确地工作。网络中其他进程会信赖这个进程，把它当作能够协调分布式行动的领导人。像 <a target="_blank" rel="noopener" href="https://raft.github.io/">Raft</a> 或者 <a target="_blank" rel="noopener" href="https://web.stanford.edu/class/cs347/reading/zab.pdf">Zab</a> 这样的协议就依赖领导人进程来协调行动。</p>
<p>这种机制会导致瓶颈集中在领导人那里，而且之前还需要领导人选举，这些多余过程可能是我们不需要的。</p>
<h2 id="一致共识consensus">一致共识CONSENSUS</h2>
<p>共识（consensus 或 agreement）问题是由 Pease ， Shostak 和 Lamport 在论文<a target="_blank" rel="noopener" href="http://research.microsoft.com/en-us/um/people/lamport/pubs/reaching.pdf">“在存在失效的情况下达成一致”</a>首先提出来的。他们是这么描述的：</p>
<p>“容错系统通常要求提供一种手段，使得独立的处理器或者进程能够达成某种精确的相互一致。例如，一个冗余系统的多个处理器可能需要定期同步它们的内部时钟。或者每个处理从某个时变的输入传感器读取的数值都有稍微不同，它们需要确定一个统一的值。”</p>
<p>共识是在独立进程之间达成一致的统一意见，这些进程会就某个问题建议一个数值，基于这个推荐的值会同意采取一致行动。</p>
<p>一个进程实现共识是通过暴露带有<strong>推荐和决定</strong>功能的API实现的，一个进程会推荐数值，由此开始共识，然后它得基于一个数值决定，这个数值是在整个系统中被推荐了的，这些算法包括：Termination, Validity, Integrity 和Agreement.</p>
<ol type="1">
<li><p><strong>Termination</strong>: 每个正确的进程最终会决定某个数值。</p></li>
<li><p><strong>Validity</strong>: 如果一个进程决定了v，那么v会被其他进程推荐。</p></li>
<li><p><strong>Integrity</strong>: 没有进程能够决定两次</p></li>
<li><p><strong>Agreement</strong>: 没有两个正确进程有不同的决定。</p></li>
</ol>
<p><strong>法定人数QUORUMS</strong></p>
<p>Quorums 是一个设计失败容错分布式系统的工具，当系统存在crash-failure模型时，总是有一个法定人数代表大多数意见从而进行决策的，因为崩溃失败的总是少数。</p>
<p>比如有N个进程服务器，假设崩溃的进程是少数，比如N/2-1个进程崩溃，也就是49%的进程崩溃，我们还是有51%的会投赞成票。Raft协议使用的是这种大多数策略，根据提交到系统的日志来判断，</p>
<h2 id="分布式系统的时间">分布式系统的时间</h2>
<p>理解时间和其导致的因果是分布式系统的大问题，我们通常用事件这个概念代表生活中发生的那些事实，使用happened before顺序约束定义这些事件，但是我们有很多进程交换信息，共同访问共享资源等等，我们如何告诉某个进程事件的happened before策略呢？也就是谁在前谁在后的顺序呢？为了回答这个问题，进程需要共享一个同步的时钟，精确知道它在网络间移动花费多长时间？包括CPU调度任务的时间等等，显然这在真实世界是不可能实现的。</p>
<p>Time, Clocks, and the Ordering of Events in a Distributed System这篇论文引入了逻辑时钟概念，逻辑时钟是一个分配一个数字给事件的方式，也就是说，这些数字不是和实际时间有关，但是和一个节点的进程事件有关。</p>
<p>有各种逻辑时钟，比如 Vector Clocks向量时钟或 Interval Tree Clocks.</p>
<p>理解分布式时间问题，必须理解一个重要概念：同时性这个想法有时我们必须放弃（The idea of simultaneity is something we have to let go.），这是有关“绝对知识”等旧哲学信条的问题，他们认为绝对知识是可以到达的，其实人的认识是相对，永远不可能到达真正事物本质，你以为的同时性并不是真正同时性，光线也是有速度的，即使最快的光线也是需要时间才从一个地方到达另外一个地方。可见Inventing the Enemy发明敌人 一书中的“绝对与相对”。</p>

    </div>

    
    
    
      
  <div class="popular-posts-header">相关文章推荐</div>
  <ul class="popular-posts">
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="/posts/ef92d986.html" rel="bookmark">【分布式共识三】拜占庭将军问题——书面协议</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="/posts/fe0496d6.html" rel="bookmark">【分布式共识二】拜占庭将军问题——口头协议</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="/posts/a7b53d58.html" rel="bookmark">【分布式共识四】POW共识算法</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="/posts/126665fc.html" rel="bookmark">IPOS共识算法设计</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="/posts/e5f8fc7.html" rel="bookmark">深入Tendermint --- 出块节点选择</a></div>
    </li>
  </ul>


    <footer class="post-footer">
          

<div class="post-copyright">
<ul>
  <li class="post-copyright-author">
      <strong>原作者： </strong>吴寿鹤
  </li>
  <li class="post-copyright-link">
      <strong>本文链接：</strong>
      <a href="https://www.whatsblockchain.com/posts/ec5b8a8d.html" title="【分布式共识一】分布系统及共识介绍">https://www.whatsblockchain.com/posts/ec5b8a8d.html</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

          <div class="post-tags">
              <a href="/tags/%E5%88%86%E5%B8%83%E5%BC%8F%E5%85%B1%E8%AF%86/" rel="tag"># 分布式共识</a>
              <a href="/tags/%E5%8C%BA%E5%9D%97%E9%93%BE%E5%85%B1%E8%AF%86%E7%AE%97%E6%B3%95/" rel="tag"># 区块链共识算法</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/posts/fe0496d6.html" rel="prev" title="【分布式共识二】拜占庭将军问题——口头协议">
                  <i class="fa fa-chevron-left"></i> 【分布式共识二】拜占庭将军问题——口头协议
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/posts/ef92d986.html" rel="next" title="【分布式共识三】拜占庭将军问题——书面协议">
                  【分布式共识三】拜占庭将军问题——书面协议 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
  
  
  



      

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

    </div>
  </main>

  <footer class="footer">
    <div class="footer-inner">
      

      

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">吴寿鹤</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
      <span>站点总字数：</span>
    <span title="站点总字数">87k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
      <span>站点阅读时长 &asymp;</span>
    <span title="站点阅读时长">1:19</span>
  </span>
</div>
<div class="busuanzi-count">
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.0/lib/anime.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script>

  
  <script>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>


















  
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>








  

  
      <script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              const target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    const script = document.createElement('script');
    script.src = '//cdn.jsdelivr.net/npm/mathjax@3.1.0/es5/tex-mml-chtml.js';
    script.defer = true;
    document.head.appendChild(script);
  } else {
    MathJax.startup.document.state(0);
    MathJax.typesetClear();
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  

</body>
</html>
